CS184 Homework 1

Overview

In this homework we implemented a basic rasteriser. We then applied textures to the shapes that we rasterised and explored different methods of preventing aliasing in the images we were rendering. We also implemented a set of basic transforms. I found the level-sampling part the most interesting to implement as I hadn't thought about using gradients in that way. I really enjoyed being able interpolate using barycentric coordinates. The colour wheel that we created looked really nice,

Task 1: Drawing Single-Color Triangles

Walk through how you rasterize triangles in your own words.

I begin by calculating the min_x, min_y, max_x, and max_y for my triangle. These four variables define a bounding box that my triangle will exist in and ensures that we are not unnecessarily checking whether points are on the triangle.

Then, I have a double for-loop that loops through each point inside of that bounding box x from min_x to max_x and y from min_y to max_y. For each pairing of x and y, we perform three line tests (with x + 0.5 and y + 0.5). These line tests are performed by calling the line_test helper function I defined. The line_test helper function calculates the following equations:

ΔXi = xi+1 − xi

ΔYi = yi+1 − yi

And then results the truth value of:

−(x − xi) · ΔYi + (y − yi) · ΔXi ≥ 0

We call this function for i = 0, 1, and 2. If all three function calls return true, we call rasterize_point to draw a point at x and y.

If it doesn’t we test the reverse order i = 2, 1, and 0 so that we can support both clockwise and counter-clockwise orderings of the points.

Explain how your algorithm is no worse than one that checks each sample within the bounding box of the triangle. The bounding box of the triangle is defined as the smallest rectangle that can be drawn whilst ensuring that the entire triangle is within it.

As mentioned in the previous answer, we begin by calculating min_x, min_y, max_x, and max_y. We then use these variables to define the bounds of my for loops. This limits the amount of points that the line test is performed on to:

p = (xmax − xmin) × (ymax − ymin)

This is equivalent to the number of points in the bounding box. Therefore, by restricting my for loops to these limits, we are checking each sample within the bounding box of the triangle. My algorithm’s performance is therefore the same as the algorithm described in the question.

Show a png screenshot of basic/test4.svg with the default viewing parameters and with the pixel inspector centered on an interesting part of the scene.

Explain any special optimizations you did beyond simple bounding box triangle rasterization, with a timing comparison table (we suggest using the c++ clock() function around the svg.draw() command in DrawRend::redraw() to compare millisecond timings with your various optimizations off and on).

The first optimisation I wrote was moving the calculations of ΔXi and ΔYi out of the for-loop as they do not have to be repeated.

This lead to a small change in average time to draw on my computer. With the average of five runs, pre-optimisation being 0.567 ms, and after the optimisation being 0.537 ms.

The next thing I noticed that evaluating the line test in reverse order was equivalent to evaluating in the original order everything was ≤ 0. So I stored these results from the first evaluation and simplified my code to:

for(int x = min_x; x <= max_x; x++ ) {
  for(int y = min_y; y <= max_y; y++ ) {
    float px = x + 0.5;
    float py = y + 0.5;

    float L0 = -1 * (px - x0) * dY_01 + (py - y0) * dX_01;
    float L1 = -1 * (px - x1) * dY_12 + (py - y1) * dX_12;
    float L2 = -1 * (px - x2) * dY_20 + (py - y2) * dX_20;

    if((L0 >= 0 && L1 >= 0 && L2 >= 0) || (L0 <= 0 && L1 <= 0 && L2 <= 0)){
      fill_pixel(x, y, color);
    }
  }
}

This reduced the average execution time to 0.407ms. Without the aforementioned change in where delta was being calculated, the average time was 0.417ms. This suggests that that optimisation is still relevant.

The last optimisation I tried was “fixing” the winding to be a consistent order before doing the double for-loop. The goal here was to reduce the number of comparisons. This reduced the time needed to 0.364ms. And 0.347ms if you included the aforementioned change in where delta was being calculated.

Task 2: Antialiasing by Supersampling

Walk through your supersampling algorithm and data structures. Why is supersampling useful? What modifications did you make to the rasterization pipeline in the process? Explain how you used supersampling to antialias your triangles.

To implement supersampling, I began by increasing the size of sample_buffer from width * height to width * height * sample_rate. This would mean that for each pixel on the screen, the sample_buffer would have a sample_rate number of data points it could average from. This required changing set_sample_rate and set_framebuffer_target.

After making that change, I edited resolve_to_framebuffer to iterate through each points samples and average them out:

Color col = Color(0, 0, 0);
for (int s = 0; s < sample_rate; ++s) {
  col += sample_buffer[(y * width + x) * sample_rate + s];
}
col *= (1.0 / sample_rate);

I then edited fill_pixel to each of the pixel’s samples to the same colour.

Lastly, I modified rasterize_triangle to also loop through every point’s samples and determine if that sample was in the triangle using the line tests. Then, if it was, I would write to that sample directly in the sample_buffer:

for (int s_x = 0; s_x < sqrt(sample_rate); s_x++) {
  for (int s_y = 0; s_y < sqrt(sample_rate); s_y++) {
    float px = x + (s_x + 0.5) / sqrt(sample_rate);
    float py = y + (s_y + 0.5) / sqrt(sample_rate);


    float L0 = -1 * (px - x0) * dY_01 + (py - y0) * dX_01;
    float L1 = -1 * (px - x1) * dY_12 + (py - y1) * dX_12;
    float L2 = -1 * (px - x2) * dY_20 + (py - y2) * dX_20;

    if(L0 >= 0 && L1 >= 0 && L2 >= 0){
      int s = s_y * sqrt(sample_rate) + s_x;
      sample_buffer[(y * width + x) * sample_rate + s] = color;
    }
  }
}

By supersampling in rasterize_triangle, we are approximating 1-pixel box filter using the average of the samples within the pixel. This produces smoother edges because points on edges have a lighter colour because there are fewer samples in the triangle. This reduces the visual harshness of the jaggies, which makes it a form of antialiasing.

Supersampling is useful because it produces smoother images. It is also useful because a point can be partially within a triangle and supersampling at a sufficiently high rate can make these thin parts of the triangle visible.

Show png screenshots of basic/test4.svg with the default viewing parameters and sample rates 1, 4, and 16 to compare them side-by-side. Position the pixel inspector over an area that showcases the effect dramatically; for example, a very skinny triangle corner. Explain why these results are observed.

We can see that with higher sample rates, very skinny portions of the triangle are now rendered. This is because while the middle of the pixel may not always have been in the triangle when other parts of the pixel were. By sampling we test smaller areas and then average out their colours to set the colour of the pixel. This captures when the pixel is partially in the triangle better without having to increase the resolution.

Additionally, we can see that at higher sample rates, every pixel is not the exact same colour. This is because of the averaging of samples. This produces smoother edges when pixels are partially in the triangle (which is the case for many of the pixels in the focused area).

Extra credit: If you implemented alternative antialiasing methods, describe them and include comparison pictures demonstrating the difference between your method and grid-based supersampling.

I implemented jitter sampling. Instead of evenly divided samples, I sampled a random number of samples within the point based on sample_rate and then averaged them out:

for (int s = 0; s < sample_rate; s++) {
  float px = x + ((float)rand() / RAND_MAX);
  float py = y + ((float)rand() / RAND_MAX);

  float L0 = -1 * (px - x0) * dY_01 + (py - y0) * dX_01;
  float L1 = -1 * (px - x1) * dY_12 + (py - y1) * dX_12;
  float L2 = -1 * (px - x2) * dY_20 + (py - y2) * dX_20;

  if(L0 >= 0 && L1 >= 0 && L2 >= 0){
    sample_buffer[(y * width + x) * sample_rate + s] = color;
  }
}

The results of rendering test4 were:

The same section is highlighted as above. Interestingly with a sample rate of 1, the image is an improvement on the previous render. At a sample rate of 4, it looks significantly worse than the previous variant. The sample rate of 16 is alright, however, it is still not as smooth as the previous render.

Because of the randomness of these samples, when I was testing, I would occasionally see really good results and occasionally really bad results. This is because this sampling method is non-deterministic.

Task 3: Transforms

Create an updated version of svg/transforms/robot.svg with cubeman doing something more interesting, like waving or running. Feel free to change his colors or proportions to suit your creativity. Save your svg file as my_robot.svg in your docs/ directory and show a png screenshot of your rendered drawing in your write-up. Explain what you were trying to do with cubeman in words.

Above is a drawing where the robot is doing a jumping jack. To produce this image I rotated the arms and legs of the robot man. I also added some transforms so that the arms and legs were still attached to the robot man.

Extra Credit: Add an extra feature to the GUI. For example, you could make two unused keys to rotate the viewport. Save an example image to demonstrate your feature, and write about how you modified the SVG to NDC and NDC to screen-space matrix stack to implement it.

I implemented a feature where you could press the “R” key to rotate the image by 90 degrees. It would then loop back from 270 degrees to 0 degrees.

To implement this I did not need to change SVG to NDC but I changed the transformation applied to ndc_to_screen. I used a translate, followed by a rotate, followed by another translate to simulate a rotation around the centre point:

ndc_to_screen = translate(width/2.0, height/2.0) * rotate(rotation_degree) * translate(-(width/2.0), -(height/2.0)) * ndc_to_screen;

You can read these operations from right-to-left. This means that the first operation being the leftwards translation.

Here are some images that show the robot rotated 0, 90, 180, and 270 degrees:

Task 4: Barycentric coordinates

Explain barycentric coordinates in your own words and use an image to aid you in your explanation. One idea is to use a svg file that plots a single triangle with one red, one green, and one blue vertex, which should produce a smoothly blended color triangle.

Barycentric coordinates are a method of expressing a position within a triangle as a linear combination with three coefficients and the three points that make up the triangle:

P = λa A + λb B + λc C

Each coefficient is equivalent to the ratio of the signed area between the coordinate's point and the two other points of the triangle and the area of the triangle (eg. λA = PBC / ABC).

The coefficients sum to 1 because the sum of these sub-triangles’ area is equal to the triangle’s area.

The benefit of this is that we can use these coefficients to linearly interpolate values inside the triangle. For example, if we assigned each point to red, green, or blue. We can use the coefficients from barycentric coordinates to create a perfectly mixed colour triangle:

Each point in the triangle has a unique colour that is determined by mixing red, green, and blue based on their position in the triangle.

Show a png screenshot of svg/basic/test7.svg with default viewing parameters and sample rate 1. If you make any additional images with color gradients, include them.

Task 5: “Pixel sampling” for texture mapping

Explain pixel sampling in your own words and describe how you implemented it to perform texture mapping. Briefly discuss the two different pixel sampling methods, nearest and bilinear.

When you want to apply a texture to a shape in your graphic, for each pixel in your object, you sample a pixel from the texture. Based on the height and width of the texture, you can calculate the corresponding pixel from a pixel’s barycentric coordinate coefficients multiplied by the triangle’s vertices (this multiplication gives you a 2D position vector from 0 to 1 that you then scale). This means that the texture is evenly mapped across the object.

Nearest pixel mapping simply calculates the nearest texel in the texture and uses that. Bilinear sampling uses a weighted average of 4 surrounding texels. It weights these the using the fractional offsets of the calculated pixel.

Check out the svg files in the svg/texmap/ directory. Use the pixel inspector to find a good example of where bilinear sampling clearly defeats nearest sampling. Show and compare four png screenshots using nearest sampling at 1 sample per pixel, nearest sampling at 16 samples per pixel, bilinear sampling at 1 sample per pixel, and bilinear sampling at 16 samples per pixel.

	1 sample/pixel	16 samples/pixel
Nearest
Bilinear

	1 sample/pixel	16 samples/pixel
Nearest
Bilinear

	1 sample/pixel	16 samples/pixel
Nearest
Bilinear

	1 sample/pixel	16 samples/pixel
Nearest
Bilinear

Comment on the relative differences. Discuss when there will be a large difference between the two methods and why

Bilinear sampling generally has less artifacts (see the example of the bird image). The textures are less sharp and slightly blurred when you zoom in. This is because each pixel is a blend of the four nearest pixels around its point in the texture. This blends nearby pixels together and the image looks smoother and more realistic. Bilinear sampling also better handles thin lines (see the map, with 1 sample/pixel). This is because if the line is thin, the nearest pixel may not always be the pixel with a line.

There is a larger difference between the two methods when the sample per pixel is lower. This is because at higher sampling rates, we are sampling the texture more and therefore are receiving back pixels that are closer to each other in the texture. The difference between samples is smaller so that image looks smoother with either method.

Task 6: “Level sampling” with mipmaps for texture mapping

Explain level sampling in your own words and describe how you implemented it for texture mapping.

When we have a texture, we can generate multiple “levels” for the texture. Each level is of a lower resolution. Level 0 has the highest resolution. We precompute these levels, we call these mipmaps. When rendering an image, nearby objects are rendered with the lowest level while objects that are further away are rendered with higher levels. To sample a level for a specific point, my implementation begins by the position’s gradient at that point (using its barycentric coordinates). These gradients serve as an approximation for depth. We then normalise the gradients and take the maximum normalised gradient (we calculate both the gradient on the y-axis and the gradient on the x-axis), this value logged by 2 is our “level”. Higher gradients are further away and therefore a higher level.

You can now adjust your sampling technique by selecting pixel sampling, level sampling, or the number of samples per pixel. Describe the tradeoffs between speed, memory usage, and antialiasing power between the three various techniques.

When implementing antialiasing, pixel sampling and level sampling use less memory compared to increasing the number of samples per pixel as when you increase the number of samples per pixel, the sample buffer grows linearly. Level sampling uses more memory than pixel sampling because it needs to store the levels.

Increasing the number of samples per pixel also linearly increases the time taken by the program so this is not a computationally effective method of antialiasing (test6.svg, on average, takes 8.546s to render with one sample per pixel and 103.971s with 16 samples per pixel).

Pixel sampling (bilinear) requires a small amount of additional computation that slightly increases the time to render an image (test6.svg, on average, takes 8.546s to render with nearest sampling and 10.379s with bilinear).

Level sampling also requires additional computation. test6.svg, on average, takes 10.516s to render with nearest level and 12.677s with bilinear level interpolation.

Pixel sampling and level sampling both effectively anti-aliased the images that we tested on. They do so using significantly less memory and significantly faster compared to increasing the samples per pixel.

Using a png file you find yourself, show us four versions of the image, using the combinations of L_ZERO and P_NEAREST, L_ZERO and P_LINEAR, L_NEAREST and P_NEAREST, as well as L_NEAREST and P_LINEAR.

	P_NEAREST	P_LINEAR
L_ZERO
L_NEAREST

	P_NEAREST	P_LINEAR
L_ZERO
L_NEAREST